\documentclass[12pt]{article}
\usepackage{epsf,epic,eepic,eepicemu}
%\documentstyle[epsf,epic,eepic,eepicemu]{article}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage{hyperref}
\usepackage{graphicx}
\hypersetup{
    colorlinks,%
    citecolor=black,%
    filecolor=black,%
    linkcolor=black,%
    urlcolor=black
    }

\begin{document}
%\oddsidemargin=-5mm \evensidemargin=-5mm \marginparwidth=.08in
%\marginparsep=.01in \marginparpush=5pt \topmargin=-15mm
%\headheight=12pt \headsep=25pt \footheight=12pt \footskip=30pt
%\textheight=25cm \textwidth=17cm \columnsep=2mm \columnseprule=1pt
%\parindent=15pt\parskip=2pt

\begin{center}
\bf Semestrální projekt MI-PAP 2011/2012:\\[5mm]
    Algoritmus pro řešení problému paralelizace řadících algoritmů Shearsort, Bitonicsort, Even-odd mergesort \\[5mm]
       Bohuslav Mach\\
       Martin Ledvinka\\[2mm]
magisterské studium, FIT ČVUT, Kolejní 550/2, 160 00 Praha 6\\[2mm]
\today
\end{center}

\section{Definice problému a popis sekvenčních algoritmů}
Cílem tohoto projektu je implementace tří řadících algoritmů - Shearsort, Bitonicsort a Even-odd mergesort. V první části jsou tyto algoritmy implementovány sekvenčně, v dalších dvou částech se pak dostáváme k hlavní náplni našeho projektu a to je jejich paralelizace pomocí technologií OpenMP a CUDA.

Vstupem každého z těchto algoritmů je (neseřazené) pole prvků načítané programem ze vstupního souboru a výstupem pak pole seřazené. Snahou je docílit zrychlení algoritmů pomocí jejich paralelizace a alespoň u jednoho z nich dosáhnout zrychlení lineárního.

\subsection{Shearsort}
Řadící algoritmus Shearsort využívá řadící algoritmus Bubblesort jako podpůrnou složku pro řazení vertikálních a horizontálních sekvencí. Jelikož slouží primárně pro řazení 2D polí, je vstupní 1D pole namapováno na 2D pole. Může se stát, že takto zadané pole nepůjde vhodně namapovat tak, aby se nám ve výsledku neobjevily \uv{díry}. S tím algoritmus počítá - tyto oblasti jsou přesunuty na začátek 2D pole, kde neovlivňují proces řazení.

\subsection{Bitonicsort}
Bitonicsort je jedním z takzvaných Batcherových algoritmů a využívá k třídění vlastností bitonických posloupností. Pro sekvenční implementaci jsme měli 2 možnosti, buď zvolit řešení využívající rekurzi a nebo řešení pomocí nerekurzivních vnořených cyklů. Z důvodu názornosti a implementační jednoduchosti jsme zvolili řešení rekurzivní, také s ohledem na to, že jsme věděli, že si stejně vnořené cykly vyzkoušíme v paralelní části.

Běžné implementace Bitonicsortu obvykle vyžadují počet prvků v poli roven $2^k$. Naše implementace je upravená tak, že funguje pro jakýkoliv kladný počet prvků tříděného pole (počet prvků se ovšem musí vejít do typu unsigned long jazyka C++).

\subsection{Even-odd mergesort}
Even-odd merge sort, nazývaný také po svém objeviteli Batcherův odd-even merge sort je, podobně jako Bitonicsort, určen pro třídící sítě, které postupně slévají dohromady seřazené podmnožiny dat. Even-odd merge sort spojuje v každé fázi dvě posloupnosti tak, že vždy porovnává sudé prvky jedné sekvence s lichými prvky druhé sekvence a naopak. Stejně jako u Bitonicsortu, jelikož algoritmus slévá postupně podsekvence délky N do jedné sekvence délky 2N, je počet slévacích fází roven logaritmu počtu prvků řazené množiny.

\section{Popis paralelních algoritmů a jejich implementace v OpenMP}
V této kapitole popíšeme jednotlivé algoritmy, jejich implementaci pomocí technologie OpenMP a změny provedené oproti sekvenčnímu řešení.

\subsection{Shearsort}
U tohoto algoritmu je snahou paralelizovat jednotlivé horizontální a vertikální sekvence řazení. To je možné vzhledem k tomu, že v každé sekvenci se řadí jednotlivé sloupce nebo řádky a tedy se v rámci jedné sekvence navzájem neovlivňují. V současné verzi prozatím není paralelizován Bubblesort, který je využíván k řazení jednotlivých sloupců a řádků v rámci dílčích sekvencí. 

Jedním z požadavků OpenMP je nutnost nezávislosti paralelizovaných cyklů. Z tohoto důvodu musel být kód sekvenčního řešení mírně upraven tak, aby tento požadavek splňoval (především se jednalo o úpravu inicializace stavových proměnných v jednotlivých částech for-cyklů).

\subsection{BitonicSort}
Jak již bylo řečeno výše, pro paralelní část jsme museli rekurzivní konstrukci sekvenční implementace rozepsat do vnořených for cyklů. Jelikož pro správnost řazení je nutno zachovat pořadí třídících fází, je využití paralelismu celkem nasnadě, paralelně se mnohem lépe spojují bitonické podposloupnosti do jedné. Abychom ale nevytvářeli paralelní vlákna opakovaně, vytvořili jsme je okamžitě při spuštění vnějšího cyklu (který určuje počet merge fází) s tím, že jejich plný potenciál se využije právě až při slévání podposloupností.

\subsection{EvenOdd Mergesort}
Pro implementaci EvenOdd mergesortu jsme vystřídali několik strategií, původně jsme ho chtěli implementovat podobně jako Bitonicsort pomocí vnořených cyklů, později jsme zkusili implementaci s explicitním zásobníkem, kterým jsme simulovali probíhající rekurzivní řazení a slévání podposloupností. 

Nakonec jsme zvolili implementaci, ve které se merge provádí v cyklech a pro řazení podposloupností v průběhu operace merge jsme zvolili sekvenční knihovní funkci sort, která se ukázala jako výrazně efektivnější než námi zkoušená řešení.

\section{Popis paralelních algoritmů a jejich implementace v CUDA}
V této sekci popíšeme naši implementaci řadících algoritmů na platformě CUDA. Vzhledem k nedostatku času a naší neznalosti této platformy jsme vzali zavděk existujícími ukázkovými kódy a inspirovali jsme se jimi při vývoji našeho řešení.

U platformy CUDA jsme především museli pamatovat na to, že větší pole se nevejdou do paměti streaming multiprocesoru (obv. 16kB) a proto jsme pracovali se dvěma variantami řešení.

Zajímavým oříškem při testování implementací na grafickém serveru bylo napsání Makefile, které nám zabralo opravdu hodně času.

\subsection{Shearsort}
Pro implementaci tohoto algoritmu jsme vycházeli z paralelního řešení v technologii OpenMP. For-cykly paralelizované v předloze byly odstraněny a nahrazeny paralelním zpracováním v technologii CUDA. Počet vláken se pro každou část výpočtu rovná počtu řádků/sloupců (v závislosti na právě probíhající fázi), jelikož algoritmus řazení je k tomu uzpůsoben.

\subsection{BitonicSort}
Implementace algoritmu BitonicSort na platformě CUDA vychází z paralelního řešení pod OpenMP a částečně je inspirována ukázkovou implementací od nvidia. Podstatné je, že řešení se skládá ze dvou částí.

První část funguje pro pole, která se vejdou do předem definované velikosti shared paměti čipu. Toto pole je zkopírováno do shared paměti, nad kterou se mnohem rychleji pracuje. Pokud se pole do této paměti nevejde, probíhá řazení tak, že fáze, ve kterých se pole do shared paměti vejde, jsou řazeny opět zkopírováním a řazením nad shared pamětí. Ve fázích, kdy se podposloupnosti do shared paměti nevejdou, probíhá řazení přímo nad globální pamětí.

\subsection{EvenOdd Mergesort}
EvenOdd mergesort se v mnohém podobá implementaci BitonicSortu, také zde jsou dvě varianty, podle velikosti řazené posloupnosti. V případě operace merge jsme u této implementace museli upustit od řazení pomocí knihovní funkce sort a místo toho jsme použili for cyklus, který rekurzi simuluje (dělí řazený interval vždy na půl a tyto poloviny třídí).

\section{Naměřené výsledky a vyhodnocení}

\subsection{OpenMP}
Aby byly výsledky měření vypovídající, rozhodli jsme se provádět měření na množinách s 262 144, 16 777 216 a 67 108 864 prvky, které byly jednorázově náhodně vygenerované. Pro Shearsort jsme kvůli horšímu výkonu zvolili instance s 65 536, 262 144 a 524 288 prvky. Jak je vidět z následujících tabulek, pro každou množinu a algoritmus bylo provedeno meření pro 1, 2, 4, 8 a 12 vláken. Všechny výsledky v tabulkách jsou průměrem z 10 měření dané instance s daným počtem vláken.

\begin{table}[ht]
\begin{center}
\begin{tabular}{| l | c | c | c | c | c |}
\hline
\textbf{Prvků} & \textbf{65536} & \textbf{262144} & \textbf{524288} \\ \hline
\textbf{Vláken (t)} & \textbf{T(n, t)/s} & \textbf{T(n, t)/s} & \textbf{T(n, t)/s} \\ \hline
1 & 7.2680 & 102.4439 & 444.4257 \\ \hline
2 & 6.7602 & 103.0747 & 446.9680 \\ \hline
4 & 7.3401 & 104.0885 & 404.0372 \\ \hline
6 & 7.5927 & 103.8522 & 375.1884 \\ \hline
8 & 7.6569 & 106.8838 & 455.6068 \\ \hline
12 & 7.7016 & 107.7658 & 434.2753 \\ \hline
\end{tabular}
\caption{OpenMP - Výsledky měření doby běhu algoritmu Shearsort pro různé instance v závislosti na počtu vláken.}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{| l | c | c | c | c | c |}
\hline
\textbf{Prvků} & \textbf{262144} & \textbf{16777216} & \textbf{67108864} \\ \hline
\textbf{Vláken (t)} & \textbf{T(n, t)/s} & \textbf{T(n, t)/s} & \textbf{T(n, t)/s} \\ \hline
1 & 0.6069 & 76.0663 & 364.7063 \\ \hline
2 & 0.3681 & 39.4214 & 194.0714 \\ \hline
4 & 0.2178 & 17.8422 & 91.0579 \\ \hline
6 & 0.1950 & 14.2548 & 65.7259 \\ \hline
8 & 0.1845 & 10.4815 & 51.2876 \\ \hline
12 & 0.1365 & 7.0757 & 33.3523 \\ \hline
\end{tabular}
\caption{OpenMP - Výsledky měření doby běhu algoritmu BitonicSort pro různé instance v závislosti na počtu vláken.}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{| l | c | c | c | c | c |}
\hline
\textbf{Prvků} & \textbf{262144} & \textbf{16777216} & \textbf{67108864} \\ \hline
\textbf{Vláken (t)} & \textbf{T(n, t)/s} & \textbf{T(n, t)/s} & \textbf{T(n, t)/s} \\ \hline
1 & 0.1705 & 16.4026 & 129.9133 \\ \hline
2 & 0.1242 & 10.7534 & 80.4380 \\ \hline
4 & 0.0980 & 7.5863 & 64.5441 \\ \hline
6 & 0.0713 & 5.1214 & 55.7218 \\ \hline
8 & 0.0648 & 4.5568 & 40.4312 \\ \hline
12 & 0.0415 & 3.9486 & 30.8714 \\ \hline
\end{tabular}
\caption{OpenMP - Výsledky měření doby běhu algoritmu EvenOdd Mergesort pro různé instance v závislosti na počtu vláken.}
\end{center}
\end{table}

\begin{figure}[ht]
\includegraphics[scale=0.47]{bitonic_even_openmp.png} 
\caption{OpenMP - Graf závislosti času výpočtu na počtu vláken pro n = 16777216.}
\end{figure}

\subsubsection{Efektivita paralelního návrhu}
Jak se v našich měřeních ukázalo, paralelní implementace Bitonicsortu dosahuje přibližně lineárního zrychlení. Také se ukázalo, že pole s cca 260 tisíci prvky je pro měření efektivity paralelního návrhu téměř nedostatečné, protože čas řazení (přinejmenším u Bitonicsortu a EvenOdd Mergesortu) je tak nízký, že režie na vytváření vláken a jejich správa se již nezanedbatelně promítá do výsledného času. Proto podle nás nedosáhl BitonicSort u tohoto pole lineárního zrychlení. U algoritmu EvenOdd Mergesort se nám ani přes veškerou snahu nepodařilo dosáhnout plně lineárního zrychlení (Zrychlení je přibližně 1.5-násobné). 

Dalším pozorovaným výsledkem je ten, že přestože naše implementace Bitonicsortu dosahuje paralelního zrychlení, je pro menší instance oproti EvenOdd Mergesortu výrazně pomalejší. Z toho usuzujeme, že zvolená strategie paralelizace zřejmě nebyla ideální. S rostoucím počtem vláken se ale rozdíly postupně vyrovnávají (v tomto případě nejspíš vítězí více vláken nad sekvenčním sortem použitým v EvenOdd Mergesortu).

Zklamáním se pro nás stal Shearsort, který se nám nepodařilo vůbec zrychlit, přestože jsme přesvědčení, že jsme zvolili správnou strategii paralelizace. Kromě toho je Shearsort výrazně pomalejší než oba ostatní algoritmy, museli jsme kvůli tomu použít i jiná testovací data. Musíme si však uvědomit, že pro řazení sloupců/řádků je používán poměrně neefektivní BubbleSort, který má na meřené výsledky jistě svůj vliv.

\subsection{CUDA}
Pro meření algoritmů jsme se rozhodli využít stávajících nagenerovaných dat s 4096 a 65536 prvky. U Algoritmů  jsme testovali běhy pro 2, 4, 8, 16, a 32 bloků. Všechny výsledky v tabulkách jsou průměrem z 10 měření dané instance s daným počtem bloků.

\begin{table}[p]
\begin{center}
\begin{tabular}{| l | c | c | c | c | c |}
\hline
\textbf{Prvků} & \textbf{4096} & \textbf{65536} \\ \hline
\textbf{Bloků (b)} & \textbf{T(n, b)/s} & \textbf{T(n, b)/s} \\ \hline
2 & 0.879332 & 69.797180 \\ \hline
4 & 0.843553 & 69.722839 \\ \hline
8 & 0.825760 & 69.684631 \\ \hline
16 & 0.822153 & 67.774353 \\ \hline
32 & 0.812252 & 66.809052 \\ \hline
\end{tabular}
\caption{CUDA - Výsledky měření doby běhu algoritmu Shearsort pro různé instance v závislosti na počtu bloků.}
\end{center}
\end{table}

\begin{table}[p]
\begin{center}
\begin{tabular}{| l | c | c | c | c | c |}
\hline
\textbf{Prvků} & \textbf{4096} & \textbf{65536} \\ \hline
\textbf{Bloků (b)} & \textbf{T(n, b)/s} & \textbf{T(n, b)/s} \\ \hline
2 & 0.000342 & 0.006341 \\ \hline
4 & 0.000185 & 0.003832 \\ \hline
8 & 0.000185 & 0.002271 \\ \hline
16 & 0.000308 & 0.001974 \\ \hline
32 & 0.000435 & 0.001431 \\ \hline
\end{tabular}
\caption{CUDA - Výsledky měření doby běhu algoritmu BitonicSort pro různé instance v závislosti na počtu vláken.}
\end{center}
\end{table}

\begin{table}[p]
\begin{center}
\begin{tabular}{| l | c | c | c | c | c |}
\hline
\textbf{Prvků} & \textbf{4096} & \textbf{65536} \\ \hline
\textbf{Bloků (b)} & \textbf{T(n, b)/s} & \textbf{T(n, b)/s} \\ \hline
2 & 0.000446 & 0.011381 \\ \hline
4 & 0.000239 & 0.006299 \\ \hline
8 & 0.000239 & 0.003493 \\ \hline
16 & 0.000344 & 0.002736 \\ \hline
32 & 0.000485 & 0.001901 \\ \hline
\end{tabular}
\caption{CUDA - Výsledky měření doby běhu algoritmu EvenOdd Mergesort pro různé instance v závislosti na počtu vláken.}
\end{center}
\end{table}

\begin{figure}[ht]
\includegraphics[scale=0.47]{bitonic_even_cuda.png} 
\caption{CUDA - Graf závislosti času výpočtu na počtu bloků algoritmů Bitonic sort a Evenodd Mergesort pro instance n = 65536.}
\end{figure}

\subsubsection{Efektivita paralelního návrhu}
Výsledky meření algoritmů Bitonicsort a Evendodd Mergesort jsou velmi podobné těm v sekci OpenMP. Avšak narozdíl od OpenMP, kde byl BitonicSort pomalejší než EvenOdd MergeSort, zde vidíme, že je na tom pro menší počet bloků BitonicSort lépe, ale s jejich zvyšujícím se počtem se doba běhu instancí vyrovnává. U instancí s malým počtem prvků si můžeme všimnout určitého bodu zlomu, kde se výpočet začíná zpomalovat. Tento fakt přičítáme stavu, kdy je při výpočtu používáno příliš mnoho bloků.

U algoritmu Shearsort jsme rovněž měnili počet bloků, při jejichž zvyšování pozorujeme určité zrychlení, jak je patrné z údajů v tabulce. Algoritmus je nastaven tak, že pro každý řádek/sloupec je vždy jedno výpočetní vlákno, liší se počty vláken v rámci jednoho bloku.

Při samotném měření na serveru jsme několikrát pozorovali stav, kdy nám výpočet z ničeho nic "zamrzl" a nedoběhl ani pro malý počet dat (16 prvků), i když jsme předtím meřili stejné nebo řádově větší instance a nezaznamenali jsme žádný problém.

\section{Aplikace a její vstupy a výstupy}

\paragraph{Příklad spuštění aplikace OpenMP \\}
\texttt{\$ $>$ mi-pap SORT\_ALG\_NAME INPUT\_FILE THREAD\_CNT} \\
kde SORT\_ALG\_NAME = \{'shear', 'bitonic', 'evenodd'\}, INPUT\_FILE = např. array16.txt, THREAD\_CNT = počet vláken

\paragraph{Příklad spuštění aplikace CUDA \\}
\texttt{\$ $>$ mi-pap SORT\_ALG\_NAME INPUT\_FILE BLOCK\_CNT} \\
kde SORT\_ALG\_NAME = \{'shear', 'bitonic', 'evenodd'\}, INPUT\_FILE = např. array16.txt, BLOCK\_CNT = počet bloků

\paragraph{Příklad výstupu algoritmu}
\begin{verbatim}
>make
>./mi-pap bitonic ../../inputs/array16.txt 2
Reading the input array...
Finished reading, 16 numbers read.
------ Unsorted Array ------
5 4 12 9 188 5 23 15 1894 11 1 25 89 157 3213 899 
------ Sorted Array ------
1 4 5 5 9 11 12 15 23 25 89 157 188 899 1894 3213 
Time elapsed: 0.065952 s.
\end{verbatim}

\section{Závěr}
S vývojem paralelních aplikací jsme se již setkali v předmětu MI-PAR, kde jsme však k paralelizaci programu využívali pouze technologie OpenMPI. Z tohoto důvodu byl pro nás tento projekt opět něčím novým a měli jsme možnost porovnat mezi sebou tyto jednotlivé technologie a zjistit, kde jsou jejich výhody a naopak slabiny a uvědomit si, k řešení kterých problému jsou vhodnější.

Vzhledem k náročnější implementaci pomocí technologie CUDA oproti OpenMP si však myslíme, že by pro tuto část mělo být vyhrazeno harmonogramem předmětu více času než pouhých 14 dní. Tento fakt se navíc sčítá s koncem semestru, kdy jsou na studenta kladeny vyšší nároky ve všech předmětech.

\end{document}
